#include<vector>
#include<unordered_map>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
private:
    bool findItineraryCore(unordered_map<string, vector<string>>& graph, vector<string>& path,string current, int size) {
        if (path.size() == size) return true;
        auto it = graph.find(current);
        if (it != graph.end()) {
            for (int i = 0; i < it->second.size(); ++i) {
                string next = it->second[i];
                it->second.erase(it->second.begin() + i);
                path.push_back(next);
                if (findItineraryCore(graph, path, next, size))
                    return true;
                path.pop_back();
                it->second.insert(it->second.begin() + i, next);
            }
        }
        return false;

    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> graph;
        for (int i = 0; i < tickets.size(); i++) {
            graph[tickets[i][0]].push_back(tickets[i][1]);
        }
        for (auto& it : graph) {
            sort(it.second.begin(), it.second.end());
            int i = 0;
            i++;
        }
        vector<string>path;
        path.push_back("JFK");
        findItineraryCore(graph, path, "JFK", tickets.size()+1);
        return path;
    }
};

//int main() {
//    vector<vector<string>> tickets;
//    tickets.push_back({ "JFK", "SFO" });
//    tickets.push_back({ "JFK", "ATL" });
//    tickets.push_back({ "SFO", "ATL" });
//    tickets.push_back({ "ATL", "JFK" });
//    tickets.push_back({ "ATL", "SFO" });
//    Solution sol;
//    sol.findItinerary(tickets);
//}